package s12_经典算法.a5_普里姆算法.a6_克鲁斯卡尔算法;

import java.util.Arrays;

/**
 * Created by 西瓜瓜
 * Date :2022/2/27
 * Description :
 * Version :1.0
 * <p>
 * 克鲁斯卡尔算法
 */
public class KruskalAlgorithm {

    /**
     * 记录边的个数
     */
    private int edgeNum;
    /**
     * 顶点数组
     */
    private char[] vertexs;
    /**
     * 领接矩阵
     */
    private int[][] matrix;
    /**
     * 表示两个顶点不能联通的常量
     */
    private static final int INF = Integer.MAX_VALUE;

    public KruskalAlgorithm(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
        // 统计边
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if (this.matrix[i][j] != INF) {
                    this.edgeNum++;
                }
            }
        }
    }

    /**
     * 显示图的邻接矩阵
     */
    public void print() {
        for (int[] rows : matrix) {
            System.out.println(Arrays.toString(rows));
        }
    }

    /**
     * 对边进行排序处理
     * @param edges
     */
    private void sortEdges(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - i - 1; j++) {
                if(edges[j].weight > edges[j+1].weight) {
                    EData temp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }
    }

    /**
     * 返回顶点对应的下标
     * @param ch 顶点的值
     * @return
     */
    private int getPosition(char ch) {
        for(int i=0; i<vertexs.length; i++) {
            if(vertexs[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取下标为i的顶点的终点，用于判断两个顶点的终点是否相同
     * @param ends 记录各个顶点对应的终点是哪个
     * @param i 传入顶点对应的下标
     * @return 下标为i的这个顶点对应的终点的下标
     */
    private int getEnd(int[] ends, int i) {
        while(ends[i] != 0) {
            i = ends[i];
        }
        return i;
    }

    /**
     * 获取边，放入EData[]数据中，遍历该数组
     * @return
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if(matrix[i][j] != INF) {
                    edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 克鲁斯卡尔算法
     */
    public void kruskal() {
        // 表示最后结果数组的索引
        int index = 0;
        // 用于保存已有最小生成树中的每个顶点在最小生成树中的终点
        int[] ends = new int[edgeNum];
        // 创建结果数组，保存最后的最小生成树
        EData[] rets = new EData[vertexs.length-1];
        // 获取图中所有边的集合
        EData[] edges = getEdges();
        // 按照边的权值大小进行排序(从小到大）
        sortEdges(edges);
        // 遍历edges数组，将边添加到最小生成树中，判断准备加入的边是否形成回路，如果没有，就加入rets，否则不能加入
        for (int i = 0; i < edgeNum; i++) {
            // 获取第i条边的第一个顶点
            int p1 = getPosition(edges[i].start);
            // 获取第i条边的第二个顶点
            int p2 = getPosition(edges[i].end);
            // 获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(ends, p1);
            // 获取p2这个顶点在已有最小生成树中的终点
            int n = getEnd(ends, p2);
            // 是否构成回路
            if(m != n) {
                // 不构成回路
                ends[m] = n; // 设置m 在“已有最小生成树”中的终点
                rets[index++] = edges[i]; // 有一条边加入rets结果集
            }
        }

        // 统计并打印最小生成树
        System.out.println(Arrays.toString(rets));
    }

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}
        };

        KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(data, matrix);

        kruskalAlgorithm.kruskal();

    }
}

/**
 * 对象实例表示一条边
 */
class EData {
    /** 边的起点 */
    char start;
    /** 边的另外一个点 */
    char end;
    /** 边的权值 */
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
